Gradient Descent#
import numpy as np
from scipy.integrate import solve_ivp
try:
import plotly.graph_objects as go
except:
!pip install plotly
import plotly.graph_objects as go
Theory#
Oppgave 4. La \(f \colon \mathbb{R}^2 \to \mathbb{R}\) være deriverbar og la \(\mathbf{y}\colon \mathbb{R}\to \mathbb{R}^2\) være en deriverbar kurve slik at \(\mathbf{y}'(t) = -\nabla f(\mathbf{y}(t))\). Forklar hvorfor funksjonen \(f(\mathbf{y}(t))\) ikke er voksende rundt noen \(t \in \mathbb{R}\).
Strategi: Hvis \(\mathbf{y}\) er som i oppgaven ovenfor, og nærmer \(\mathbf{y}(t)\) seg et punkt \(\mathbf{x}_0\) når \(t\) blir stor så er kanskje dette punktet et lokalt minimumspunkt for \(f\). Mange steder brukes dette til å søke etter lokale minimumspunkter for \(f\). Hvis vi klarer å finne et slik punkt \(\mathbf{x}_0\) kan vi bruke andrederiverttesten til å prøve å vise at det er et lokalt minimumspunkt.
Hvis vi er gitt et startpunkt \(\mathbf{y}_0\) kan vi prøve å finne en løsning til differensialligningen \(\mathbf{y}'(t) = -\nabla f(\mathbf{y}(t))\) med startbetingelse \(\mathbf{y}(0) = \mathbf{y}_0\) og se hvilket punkt \(\mathbf{y}(t)\) går mot når \(t\) blir stor.
Lemma La \(f \colon \mathbb{R}^n \to \mathbb{R}\) være kontinuerlig deriverbar. Hvis \(\mathbf{y}(t)\) er en løsning til differensialligningen \(\mathbf{y}'(t) = -\nabla f(\mathbf{y}(t))\) og \(\lim_{t \to \infty} \mathbf{y}(t) = \mathbf{p}\) for en \(\mathbf{p} \in \mathbb{R}^n\), da er \(\nabla f(\mathbf{p}) = 0\)
Konsekvens: Siden \(f \circ \mathbf{y}\) ikke er voksende er \(\mathbf{p} = \lim_{t \to \infty} \mathbf{y}(t)\) enten et lokalt minimum eller et saddelpunkt, det vil si, et kritisk punkt for \(f\) som verken er et lokalt minimum eller et lokalt maksimum.
Forklaring: At \(f\) er kontinuerlig deriverbar betyr at funksjonen \(\mathbf{x} \mapsto \nabla f(\mathbf{x})\) er kontinuerlig.
Siden denne funksjonen er kontinuerlig og \(\lim_{t \to \infty} \mathbf{y}(t) = \mathbf{p}\) vet vi at
Derfor er $\(\lim_{t \to \infty} (f \circ \mathbf{y})'(t) = \lim_{t\to \infty} \nabla f'(\mathbf{y}(t)) \cdot \mathbf{y}'(t) = \lim_{t\to \infty} -|\nabla f(\mathbf{y}(t))|^2 = -|\nabla f(\mathbf{p})|^2.\)$
Siden er \(f\) og \(\mathbf{y}\) er deriverbare er de også kontinuerlige.
Derfor er også \((f \circ \mathbf{y})\) kontinuerlig slik at \((f \circ \mathbf{y})(t) \to f (\mathbf{p})\) for \(t \to \infty\).
Derfor kan ikke \(\lim_{t \to \infty} (f \circ \mathbf{y})'(t)\) konvergere til et tall forskjellig fra null, slik at \(\nabla f(\mathbf{p}) = 0\) er eneste mulighet.
Eksempel#
\(f(x) = e^{-x_1^2 - x_2^2}\)
# @title Plotter
def f(x):
x1, x2 = x
# bemerk at hvis x ikke er i D, da lar vi f være ikke definert, eller nan for not a number
return -np.exp(-x1**2 - x2**2)
def gradientf(x1, x2):
return np.array(2*x1*np.exp(-x1**2 - x2**2), 2*x2*np.exp(-x1**2 - x2**2))
def dy(t, y):
return -gradientf(y[0], y[1])
sol = solve_ivp(dy, t_span=[0, 100], y0=[0.5, 0.5], t_eval=np.linspace(0, 100, 1000))
# Create a grid of x and y values
x1 = np.linspace(-1, 1, 300)
x2 = np.linspace(-1, 1, 300)
#x1 = np.sign(x1) * np.sqrt(np.abs(x1))
#x2 = np.sign(x2) * np.sqrt(np.abs(x2))
x = np.meshgrid(x1, x2)
# Compute the function values
x3 = f(x)
# Create figure
fig = go.Figure()
# Add surface
fig.add_surface(
x=x[0], y=x[1], z=x3, colorscale="Viridis", opacity=0.8
)
# Add curve
fig.add_scatter3d(
x=sol.y[0], y=sol.y[1], z=f(sol.y), mode="lines", line=dict(color="red", width=10)
)
fig.show()
# @title Ny f
def f(x):
x1, x2 = x
return -(2*np.exp(-((x1 + 1)**2 + x2**2)) + np.exp(-((x1 - 2)**2 + (x2 - 0.2)**2)))
def gradientf(x):
x1 = x[0]
x2 = x[1]
return -np.array([-4*(x1 + 1)*np.exp(-(x1 + 1)**2 - x2**2) - 2*(x1 - 2)*np.exp(-((x1 - 2)**2 + (x2 - 0.2)**2)),
-4*x2*np.exp(-(x1 + 1)**2 - x2**2) - 2*(x2 - 0.2)*np.exp(-((x1 - 2)**2 + (x2 - 0.2)**2))])
def dy(t, y):
return -gradientf(y)
sol = solve_ivp(dy, t_span=[0, 100], y0=[1.5, 0.5], t_eval=np.linspace(0, 100, 1000))
sol2 = solve_ivp(dy, t_span=[0, 100], y0=[.6, 0.5], t_eval=np.linspace(0, 100, 1000))
# Create a grid of x and y values
x1 = np.linspace(-2.5, 3.5, 300)
x2 = np.linspace(-1.5, 1.5, 300)
#x1 = np.sign(x1) * np.sqrt(np.abs(x1))
#x2 = np.sign(x2) * np.sqrt(np.abs(x2))
x = np.meshgrid(x1, x2)
# Compute the function values
x3 = f(x)
# Create figure
fig = go.Figure()
# Add surface
fig.add_surface(
x=x[0], y=x[1], z=x3, colorscale="Viridis", opacity=0.8
)
# Add curve
fig.add_scatter3d(
x=sol.y[0], y=sol.y[1], z=f(sol.y), mode="lines", line=dict(color="red", width=10)
)
fig.add_scatter3d(
x=sol2.y[0], y=sol2.y[1], z=f(sol2.y), mode="lines", line=dict(color="red", width=10)
)
fig.show()
Vi vet at vi kan løse differensialligninger med Eulers metode. Hvis vi er ute etter å finne lokale kan vi spørre om hvor stor t skal være for at vi kommer tett på et lokalt minimum. I stedet for å gi t til algoritmen kan vi gi et kriterium for å stoppe når funksjonsverdien endrer seg lite. Rigger vi Eulers metode slik kalles den for “gradient descent”.
Oppgave
La \(f \colon \mathbb{R}^2 \to \mathbb{R}\) være funksjonen gitt ved
Finn gradienten til \(f\).
Plott grafen til \(f\).
Finn et lokalt minimum til \(f\) ved å bruke gradient descent, startende i punktet \(\begin{bmatrix}1\\1\end{bmatrix}\).